package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/7/2
 * Description:
 * - 有序矩阵中第K小的元素
 * 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 * 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * matrix = [
 * [ 1,  5,  9],
 * [10, 11, 13],
 * [12, 13, 15]
 * ],
 * k = 8,
 * <p>
 * 返回 13。
 * <p>
 * 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
 **/
public class Que378 {

    public static void main(String[] args) {
        int[][] a = {{1,  5,  9}, {10, 11, 13}, {12, 13, 15}};
        int k = 8;

        System.out.println(new Solution().kthSmallest(a, k));
    }

    static class Solution {

        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;

            int l = matrix[0][0];
            int r = matrix[n - 1][n - 1];

            while (l < r) {
                int mid = l + (r - l) / 2;

                if (check(matrix, mid, k))
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        }

        private static boolean check(int[][] matrix, int mid, int k) {
            int c = 0;
            int n = matrix.length;

            int i = n - 1;
            int j = 0;

            while (i >= 0 && j < n) {
                if (matrix[i][j] <= mid) {
                    c += i + 1;
                    j++;
                } else {
                    i--;
                }
            }

            return c >= k;
        }
    }
}
